253. Meeting Rooms II
Medium

Given an array of meeting time intervals intervals where intervals[i] = [starti, endi], return the minimum number of conference rooms required.

 

Example 1:

Input: intervals = [[0,30],[5,10],[15,20]]
Output: 2

Example 2:

Input: intervals = [[7,10],[2,4]]
Output: 1

 

Constraints:

  • 1 <= intervals.length <= 104
  • 0 <= starti < endi <= 106
Accepted
435,110
Submissions
916,664
Seen this question in a real interview before?
Related Topics
Show Hint 1
Think about how we would approach this problem in a very simplistic way. We will allocate rooms to meetings that occur earlier in the day v/s the ones that occur later on, right?
Show Hint 2
If you've figured out that we have to sort the meetings by their start time, the next thing to think about is how do we do the allocation?
There are two scenarios possible here for any meeting. Either there is no meeting room available and a new one has to be allocated, or a meeting room has freed up and this meeting can take place there.
Show Hint 3
An important thing to note is that we don't really care which room gets freed up while allocating a room for the current meeting. As long as a room is free, our job is done.

We already know the rooms we have allocated till now and we also know when are they due to get free because of the end times of the meetings going on in those rooms. We can simply check the room which is due to get vacated the earliest amongst all the allocated rooms.
Show Hint 4
Following up on the previous hint, we can make use of a min-heap to store the end times of the meetings in various rooms.

So, every time we want to check if any room is free or not, simply check the topmost element of the min heap as that would be the room that would get free the earliest out of all the other rooms currently occupied.

If the room we extracted from the top of the min heap isn't free, then no other room is. So, we can save time here and simply allocate a new room.

Average Rating: 4.83 (472 votes)

Premium

Solution



Intuition

This problem is very similar to something that employees of a company can face potentially on daily basis.

Suppose you work at a company and you belong to the IT department and one of your job responsibilities is securing rooms for meetings that are to happen throughout the day in the office.

You have multiple meeting rooms in the office and you want to make judicious use of them. You don't really want to keep people waiting and want to give a group of employees a room to hold the meeting right on time.

At the same time, you don't really want to use too many rooms unless absolutely necessary. It would make sense to hold meetings in different rooms provided that the meetings are colliding with each other, otherwise you want to make use of as less rooms as possible to hold all of the meetings. How do you go about it ?

I just represented a common scenario at an office where given the start and end times for meetings to happen throughout the day, you, as an IT guru need to setup and allocate the room numbers to different teams.

Let's approach this problem from the perspective of a group of people who want to hold a meeting and have not been allocated a room yet. What would they do?

This group would essentially go from one room to another and check if any meeting room is free. If they find a room that is indeed free, they would start their meeting in that room. Otherwise, they would wait for a room to be free. As soon as the room frees up, they would occupy it.

This is the basic approach that we will follow in this question. So, it is a kind of simulation but not exactly. In the worst case we can assign a new room to all of the meetings but that is not really optimal right? Unless of course they all collide with each other.

We need to be able to find out efficiently if a room is available or not for the current meeting and assign a new room only if none of the assigned rooms is currently free.

Let's look at the first approach based on the idea we just discussed.


Approach 1: Priority Queues

We can't really process the given meetings in any random order. The most basic way of processing the meetings is in increasing order of their start times and this is the order we will follow. After all, it makes sense to allocate a room to the meeting that is scheduled for 9 a.m. in the morning before you worry about the 5 p.m. meeting, right?

Let's do a dry run of an example problem with sample meeting times and see what our algorithm should be able to do efficiently.

We will consider the following meeting times for our example (1, 10), (2, 7), (3, 19), (8, 12), (10, 20), (11, 30). The first part of the tuple is the start time for the meeting and the second value represents the ending time. We are considering the meetings in a sorted order of their start times. The first diagram depicts the first three meetings where each of them requires a new room because of collisions.

The next 3 meetings start to occupy some of the existing rooms. However, the last one requires a new room altogether and overall we have to use 4 different rooms to accommodate all the meetings.

Sorting part is easy, but for every meeting how do we find out efficiently if a room is available or not? At any point in time we have multiple rooms that can be occupied and we don't really care which room is free as long as we find one when required for a new meeting.

A naive way to check if a room is available or not is to iterate on all the rooms and see if one is available when we have a new meeting at hand.

However, we can do better than this by making use of Priority Queues or the Min-Heap data structure.

Instead of manually iterating on every room that's been allocated and checking if the room is available or not, we can keep all the rooms in a min heap where the key for the min heap would be the ending time of meeting.

So, every time we want to check if any room is free or not, simply check the topmost element of the min heap as that would be the room that would get free the earliest out of all the other rooms currently occupied.

If the room we extracted from the top of the min heap isn't free, then no other room is. So, we can save time here and simply allocate a new room.

Let us look at the algorithm before moving onto the implementation.

Algorithm

  1. Sort the given meetings by their start time.
  2. Initialize a new min-heap and add the first meeting's ending time to the heap. We simply need to keep track of the ending times as that tells us when a meeting room will get free.
  3. For every meeting room check if the minimum element of the heap i.e. the room at the top of the heap is free or not.
  4. If the room is free, then we extract the topmost element and add it back with the ending time of the current meeting we are processing.
  5. If not, then we allocate a new room and add it to the heap.
  6. After processing all the meetings, the size of the heap will tell us the number of rooms allocated. This will be the minimum number of rooms needed to accommodate all the meetings.

Let us not look at the implementation for this algorithm.

Complexity Analysis

  • Time Complexity: O(NlogN)O(N\log N).

    • There are two major portions that take up time here. One is sorting of the array that takes O(NlogN)O(N\log N) considering that the array consists of NN elements.
    • Then we have the min-heap. In the worst case, all NN meetings will collide with each other. In any case we have NN add operations on the heap. In the worst case we will have NN extract-min operations as well. Overall complexity being (NlogN)(NlogN) since extract-min operation on a heap takes O(logN)O(\log N).
  • Space Complexity: O(N)O(N) because we construct the min-heap and that can contain NN elements in the worst case as described above in the time complexity section. Hence, the space complexity is O(N)O(N).


Approach 2: Chronological Ordering

Intuition

The meeting timings given to us define a chronological order of events throughout the day. We are given the start and end timings for the meetings which can help us define this ordering.

Arranging the meetings according to their start times helps us know the natural order of meetings throughout the day. However, simply knowing when a meeting starts doesn't tell us much about its duration.

We also need the meetings sorted by their ending times because an ending event essentially tells us that there must have been a corresponding starting event and more importantly, an ending event tell us that a previously occupied room has now become free.

A meeting is defined by its start and end times. However, for this specific algorithm, we need to treat the start and end times individually. This might not make sense right away because a meeting is defined by its start and end times. If we separate the two and treat them individually, then the identity of a meeting goes away. This is fine because:

When we encounter an ending event, that means that some meeting that started earlier has ended now. We are not really concerned with which meeting has ended. All we need is that some meeting ended thus making a room available.

Let us consider the same example as we did in the last approach. We have the following meetings to be scheduled: (1, 10), (2, 7), (3, 19), (8, 12), (10, 20), (11, 30). As before, the first diagram show us that the first three meetings are colliding with each other and they have to be allocated separate rooms.

The next two diagrams process the remaining meetings and we see that we can now reuse some of the existing meeting rooms. The final result is the same, we need 4 different meeting rooms to process all the meetings. That's the best we can do here.

Algorithm

  1. Separate out the start times and the end times in their separate arrays.
  2. Sort the start times and the end times separately. Note that this will mess up the original correspondence of start times and end times. They will be treated individually now.
  3. We consider two pointers: s_ptr and e_ptr which refer to start pointer and end pointer. The start pointer simply iterates over all the meetings and the end pointer helps us track if a meeting has ended and if we can reuse a room.
  4. When considering a specific meeting pointed to by s_ptr, we check if this start timing is greater than the meeting pointed to by e_ptr. If this is the case then that would mean some meeting has ended by the time the meeting at s_ptr had to start. So we can reuse one of the rooms. Otherwise, we have to allocate a new room.
  5. If a meeting has indeed ended i.e. if start[s_ptr] >= end[e_ptr], then we increment e_ptr.
  6. Repeat this process until s_ptr processes all of the meetings.

Let us not look at the implementation for this algorithm.

Complexity Analysis

  • Time Complexity: O(NlogN)O(N\log N) because all we are doing is sorting the two arrays for start timings and end timings individually and each of them would contain NN elements considering there are NN intervals.

  • Space Complexity: O(N)O(N) because we create two separate arrays of size NN, one for recording the start times and one for the end times.



Report Article Issue

Comments: 151
shuo21's avatar
Read More

Let us NOT look at the implementation for this algorithm.
I like it .

473
Show 11 replies
Reply
Share
Report
michalmichal's avatar
Read More

Great explanation, I wish every question was explained that well!

171
Show 2 replies
Reply
Share
Report
sahiti4's avatar
Read More

Those are some freakish ideas.......

81
Reply
Share
Report
mehranangelo's avatar
Read More

This is my short interview friendly solution

    public int minMeetingRooms(Interval[] intervals) {
        Arrays.sort(intervals,(a,b)->(a.start-b.start));
        PriorityQueue<Interval> pq=new PriorityQueue<>((a,b)->(a.end-b.end));
        for(Interval i:intervals){
            if(!pq.isEmpty()&&pq.peek().end<=i.start){
                pq.poll();
            }
            pq.add(i);
        }
        return pq.size();
    }

123
Show 11 replies
Reply
Share
Report
motime's avatar
Read More

Why do we need to define a comparator for PriorityQueue? Isn't it a min integer heap by default?

41
Show 6 replies
Reply
Share
Report
SuM_007's avatar
Read More

class Solution {
    public int minMeetingRooms(Interval[] intervals) {
        int[] starts = new int[intervals.length];
        int[] ends = new int[intervals.length];
        for (int i = 0; i < intervals.length; i++) {
            starts[i] = intervals[i].start;
            ends[i] = intervals[i].end;
        }
        Arrays.sort(starts);
        Arrays.sort(ends);
        int rooms = 0, endsItr = 0;
        for (int i = 0; i < starts.length; i++) {
            if (starts[i] < ends[endsItr]) {
                rooms++;
            } else {
                endsItr++;
            }
        }
        return rooms;
    }
}

80
Reply
Share
Report
enjoymrsun's avatar
Read More

absolutely 5 star solution

52
Show 1 reply
Reply
Share
Report
slow_danger's avatar
Read More

One small improvement to make this more idiomatic Java would be to use anonymous functions for the comparators:

Arrays.sort(intervals, (a, b) -> a.start - b.start);

You can also use the Integer comparison function:

Arrays.sort(intervals, (a, b) -> Integer.compare(a.start, b.start) );

19
Show 3 replies
Reply
Share
Report
a-b-c's avatar
Read More

one of the best articles on leetcode, thank you

28
Show 1 reply
Reply
Share
Report
christopherwu0529's avatar
Read More

Solution 1 is so smart

17
Show 2 replies
Reply
Share
Report
Time Submitted
Status
Runtime
Memory
Language
05/28/2021 19:07Accepted20 ms13.5 MBcpp
05/26/2021 08:29Accepted12 ms13.4 MBcpp
253/1883
Your previous code was restored from your local storage.Reset to default
Contribute
|||
Saved
#251 Flatten 2D Vector
Medium
#252 Meeting Rooms
Easy
#253 Meeting Rooms II
Medium
#254 Factor Combinations
Medium
#255 Verify Preorder Sequence in Binary Search Tree
Medium
#256 Paint House
Medium
#257 Binary Tree Paths
Easy
#258 Add Digits
Easy
#259 3Sum Smaller
Medium
#260 Single Number III
Medium
#261 Graph Valid Tree
Medium
#262 Trips and Users
Hard
#263 Ugly Number
Easy
#264 Ugly Number II
Medium
#265 Paint House II
Hard
#266 Palindrome Permutation
Easy
#267 Palindrome Permutation II
Medium
#268 Missing Number
Easy
#269 Alien Dictionary
Hard
#270 Closest Binary Search Tree Value
Easy
#271 Encode and Decode Strings
Medium
#272 Closest Binary Search Tree Value II
Hard
#273 Integer to English Words
Hard
#274 H-Index
Medium
#275 H-Index II
Medium
#276 Paint Fence
Medium
#277 Find the Celebrity
Medium
#278 First Bad Version
Easy
#279 Perfect Squares
Medium
#280 Wiggle Sort
Medium
#281 Zigzag Iterator
Medium
#282 Expression Add Operators
Hard
#283 Move Zeroes
Easy
#284 Peeking Iterator
Medium
#285 Inorder Successor in BST
Medium
#286 Walls and Gates
Medium
#287 Find the Duplicate Number
Medium
#288 Unique Word Abbreviation
Medium
#289 Game of Life
Medium
#290 Word Pattern
Easy
#291 Word Pattern II
Medium
#292 Nim Game
Easy
#293 Flip Game
Easy
#294 Flip Game II
Medium
#295 Find Median from Data Stream
Hard
#296 Best Meeting Point
Hard
#297 Serialize and Deserialize Binary Tree
Hard
#298 Binary Tree Longest Consecutive Sequence
Medium
#299 Bulls and Cows
Medium
#300 Longest Increasing Subsequence
Medium